package interview.dynamic;

/**
 * 最大和的子数组
 * https://leetcode-cn.com/problems/maximum-subarray/
 *
 * O(N)时间复杂度，只遍历一遍
 * 找递推公式:
 * p(n) 表示第n个元素结尾的 和最大的子数组
 * p(n+1) = p(n)>0? (p[n] + arr[n+1]) : arr[n+1]
 *
 * Created by yzy on 2021-02-05 16:18
 */
public class MaxSubArray {

    public int maxSubArray(int[] nums) {
        if(nums.length==0) return 0;
        int max = nums[0];
        int pn = max;
        for(int i=1; i<nums.length; i++){
            pn = pn>0 ? (pn + nums[i]) : nums[i];
            max = max > pn ? max : pn;
        }
        return max;
    }



    public int maxSubArray_2_test(int[] nums){
        if(nums.length==0){
            return 0;
        }
        int currSubMax = nums[0];
        int max = currSubMax;
        for(int i=1; i<nums.length; i++){
            currSubMax = currSubMax < 0 ? nums[i] : currSubMax+nums[i];
            max = currSubMax > max ? currSubMax : max;
        }
        return max;
    }

}
